package DataStructure.linkList;

/**
 * 25. K 个一组翻转链表 https://leetcode.cn/problems/reverse-nodes-in-k-group
 * 题目简述：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 */
public class ReverseKGroup {

    /**
     * 思路一：递归。对前k个节点(head至p)进行翻转，翻转时pre需要预先指向后面链表翻转后的头结点（递归），然后更新head并进行翻转，最后返回新头节点
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p = head;
        for (int i = 1;i < k && p != null;i++) { //找到第k个节点
            p = p.next;
        }
        if (p != null) { //若p不为null，则从head至p够k个节点，否则不翻转
            ListNode pre = reverseKGroup(p.next, k), cur = head; //使用翻转链表的方法，唯一不同的是pre需要预先指向后面链表翻转后的头结点（递归）
            head = p; //更新头结点
            p = p.next; //预先记录循环退出条件
            while (cur != p) {
                ListNode t = cur.next;
                cur.next = pre;
                pre = cur;
                cur = t;
            }
        }
        return head; //返回头结点
    }

    /**
     * 思路二：非递归。使用一个preTail指针记录已翻转链表的尾结点，nextHead记录后续待翻转链表头结点
     * 开启循环：对前k个节点(nextHead至p)进行翻转，首先更新preTail.next、preTail和nextHead，然后开启翻转
     * 若不够k个节点，则无需翻转 直接将preTail.next指向nextHead，并跳出循环
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        if (k == 1) return head;
        ListNode preTail = null, nextHead = head, result = head;
        while (nextHead != null) {
            ListNode p = nextHead;
            for (int i = 1; i < k && p != null; i++) { //找到第k个节点
                p = p.next;
            }
            if (p != null) { //一、若p不为null，则从nextHead至p够k个节点，进行翻转
                if (result == head) result = p; //1. 第一次翻转需更新result
                if (preTail != null) preTail.next = p; //2. 将preTail.next指向后续翻转后的新头结点
                preTail = nextHead; //3. 更新preTail为新链表尾结点nextHead
                ListNode pre = null, cur = nextHead; //4. 准备开启翻转
                nextHead = p.next; //5. 预先记录后续待翻转链表头结点
                while (cur != nextHead) {
                    ListNode t = cur.next;
                    cur.next = pre;
                    pre = cur;
                    cur = t;
                }
            } else { //二、否则nextHead链表无需翻转，直接将preTail.next指向nextHead，并跳出循环
                if (preTail != null) preTail.next = nextHead;
                break;
            }
        }
        return result; //返回头结点
    }

}
